class Solution {
    /*
        1. 当nums只有两个数的时候，如果我们操作到两个数接近，也就是x < =y且x*m > y，
        那么后续操作一定是在X和y两个数之间交替进行的
        2. 首先，直接暴力模拟(用最小堆)，直到原来的最大值，变成最小值
        然后，直接用公式计算出每个数还需要操作多少次
        a. 当 i < k % n时，(k / n) + 1次
        b. 当 i >= k % n时，(k / n)次
        注意这里 k / n 都是向下取整
    */
    const int MOD = 1'000'000'007;
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        if(multiplier == 1)
            return nums;

        auto comp = [&](const pair<long long, int> &p1, const pair<long long, int> &p2)->bool{
            if(p1.first == p2.first)
                return p1.second > p2.second;
            return p1.first > p2.first;
        };

        int mx = ranges::max(nums), n = nums.size();

        // 最小堆模拟
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, decltype(comp)> pq(comp);
        for(int i = 0; i < n; i++)
            pq.emplace(nums[i], i);

        while(k > 0 && pq.top().first < mx)
        {
            auto [x, i] = pq.top();
            pq.pop();
            x *= multiplier;
            pq.emplace(x, i);
            k--;
        }

        // 按照公式进行剩下操作
        // 快速幂
        auto pow = [&](long long x, int n)->long long{
            long long res = 1;
            for(; n;  n /= 2)
            {
                if(n % 2)
                    res = res * x % MOD;
                x = x * x % MOD;
            }
            return res;
        };

        // 对每个数取模
        for(int i = 0; i < n; i++)
        {
            auto [x, j] = pq.top();
            pq.pop();
            nums[j] = x % MOD * pow(multiplier, k / n + (i < k % n)) % MOD;
        }
        return nums;
    }
};